// @before-stub-for-debug-begin
#include "commonInc.h"
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=1 lang=cpp
 *
 * [1] 两数之和
 */

// @lc code=start
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int n=nums.size();
        if(n < 2)
            return {};
       
        vector<int> indices(n,0);
        for(int i=0;i<n;++i)
            indices[i]=i;
        std::sort(indices.begin(),indices.end(),[&](int l,int r)->bool
        {
            return nums[l] < nums[r];
        });

        int left=0,right=n-1;
        while(left < right)
        {
            int twoSum = nums[indices[left]] + nums[indices[right]];
            if(twoSum == target)
                return {indices[left],indices[right]};
            else if(twoSum > target)
                right--;
            else 
                left++;
        }

        return {};
    }
};
// @lc code=end